//给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 
//
// 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
//输出：3
//解释：和等于 8 的路径有 3 条，如图所示。
// 
//
// 示例 2： 
//
// 
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：3
// 
//
// 
//
// 提示: 
//
// 
// 二叉树的节点个数的范围是 [0,1000] 
// 
// -10⁹ <= Node.val <= 10⁹ 
// -1000 <= targetSum <= 1000 
// 
//
// Related Topics 树 深度优先搜索 二叉树 👍 1685 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-08-22 19:07:17
 * @description 437.路径总和 III
 */
public class PathSumIii{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new PathSumIii().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
         /*dfs，对每个节点穷举
         * rootsum即以每个节点开始，满足和为target的路径数
         * pathsum分别从当前节点，他的左右子树去调用递归
         * 时间On^2 空间on*/
    public int pathSum1(TreeNode root, int targetSum) {
        if(root==null) return 0;

        int res=rootSum(root,targetSum);
        res+=pathSum1(root.left,targetSum);
        res+=pathSum1(root.right,targetSum);
        return  res;
    }
    private int rootSum(TreeNode root,long tar){
        int res=0;

        if(root==null){
            return 0;
        }
        int val=root.val;
        if(val==tar) res++;
        res+=rootSum(root.left,tar-val);
        res+=rootSum(root.right,tar-val);
        return  res;
    }

    /*前缀和:根节点到当前节点的和
    记录后，在已保存的路径前缀和中寻找是否存在curr-target的路径
    prefix.put(0L,1);代表，root根节点的前缀和为0，出现了一次
    * 时间空间on*/
        public int pathSum(TreeNode root,int targetSum){
            Map<Long, Integer> prefix = new HashMap<Long,Integer>();
            prefix.put(0L,1);
            return dfs(root,prefix,0,targetSum);
        }
        public int dfs(TreeNode root,Map<Long,Integer> map,long curr,int targetSum){
            if(root==null){
                return 0;
            }
            int res=0;
            //加上当前值
            curr+=root.val;
            //查询有没有符合curr-target的节点
            res=map.getOrDefault(curr-targetSum,0);
//            保存当前出现在次数
            map.put(curr,map.getOrDefault(curr,0)+1);
            //加上左右子树中符合条件的数量
            res+=dfs(root.left,map,curr,targetSum);
            res+=dfs(root.right,map,curr,targetSum);
            //路径回退，去掉不再在路上的当前节点的路径和
            //因为先序遍历是遍历根、左、右，即当前节点及其所有子节点，
            // 所以当遍历完当前节点和其所以子节点之后，
            // 当前节点的前缀和就没有用了，就需要把map里的记录删除，
            // 否则会影响其他子树的计算。跟当前节点没有路径关系的节点，
            // 不需要当前节点的前缀和
            map.put(curr,map.get(curr)-1);
            return res;
        }


}
//leetcode submit region end(Prohibit modification and deletion)

}
